package com.lqian.simplestructure.linearlist.lru;

import java.util.HashMap;

/**
 * 采用双向链表手动实现LRU算法，
 *
 * redis有一种淘汰算法LRU策略
 *
 * 1、leetcode描述；
 *
 * /**
 *  *
 *  * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 *  实现 LRUCache 类：
 *  LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 *  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 *  void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
 *  如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 *  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 *
 *  示例：
 *
 *  输入
 *  ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 *  [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 *  输出
 *  [null, null, null, 1, null, -1, null, -1, 3, 4]
 *
 *  解释
 *  LRUCacheTask cacheTask = new LRUCache(2);
 *  cacheTask.put(1, 1); // 缓存是 {1=1}
 *  cacheTask.put(2, 2); // 缓存是 {1=1, 2=2}
 *  cacheTask.get(1);    // 返回 1
 *  cacheTask.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 *  cacheTask.get(2);    // 返回 -1 (未找到)
 *  cacheTask.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 *  cacheTask.get(1);    // 返回 -1 (未找到)
 *  cacheTask.get(3);    // 返回 3
 *  cacheTask.get(4);    // 返回 4
 *
 *  提示：
 *  1 <= capacity <= 3000
 *  0 <= key <= 10000
 *  0 <= value <= 105
 *  最多调用 2 * 105 次 get 和 put
 *  *
 *
 * ----------------------------------------------------
 * 如何基于链表实现 LRU 缓存淘汰算法？
 * 我的思路是这样的：我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。
 * 当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
 * 1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
 * 2. 如果此数据没有在缓存链表中，又可以分为两种情况：
 *  如果此时缓存未满，则将此结点直接插入到链表的头部；
 *  如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
 *
 * 现在我们来看下 m 缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。
 * 实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。
 */
public class LRUCache {


    private MyCache<Integer,Integer> cache;

    public LRUCache(int capacity) {
        this.cache = new MyCache<>(capacity);
    }

    public int get(int key){
        Integer ans = cache.get(key);
        return ans == null ? -1:ans;
    }

    public void put(int key ,int value){
        cache.set(key,value);
    }

    //--------------------main()---------------------------

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        int i = lruCache.get(1);
        System.out.println(i);  // 1 2  能得到
        lruCache.put(3,3);
        int i1 = lruCache.get(2); // 2 -->  1 2(X) ---> 1 3
        System.out.println(i1);
    }



    //-----------------------------------------------
    /**
     * 定义双向链表
     */
    public static class Node<K,V>{
        public K key;
        public V value;
        public Node next;
        public Node last;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    /**
     * 定义双向链表的api
     */
    public static class NodeDoubleLinkList<K,V>{
        private Node<K,V> head;
        private Node<K,V> tail;

        public NodeDoubleLinkList() {
            this.head = null;
            this.tail = null;
        }

        /**
         * 删除首节点
         */
        public Node<K,V> removeHead(){
            if (head == null) return null;
            Node<K,V> res = head;
            if (head == tail){
                head = null;
                tail = null;
            }else {
                head = res.next;
                res.next = null;
                head.last = null;
            }
            return res;
        }

        /**
         * 新增尾节点
         */
        public void addTail(Node<K,V> newNode){
            if (newNode == null) return;
            if (head == null){
                head = newNode;
                tail = newNode;
            }else {
                tail.next = newNode;
                newNode.last = tail;
                tail = newNode;
            }
        }

        /**
         * 把某个节点移动到尾节点
         */
        public void moveToTail(Node<K,V> oldNode){
            if(tail == oldNode){
                return;
            }
            if(head == oldNode){
                head = oldNode.next;
                head.last = null;
            }else {
                oldNode.last.next = oldNode.next;
                oldNode.next.last = oldNode.last;
            }
            tail.next = oldNode;
            oldNode.last = tail;
            oldNode.next = null;
            tail = oldNode;
        }

    }
    //--------------------MyCache---------------------------
    /**
     * 缓存操作的核心方法
     * @param <K>
     * @param <V>
     */
    public static class MyCache<K,V>{
        private HashMap<K,Node<K,V>> keyNodeMap;
        private NodeDoubleLinkList<K,V> nodeList;
        private final int capacity;

        public MyCache(int capacity) {
            if (capacity < 1){
                throw new RuntimeException("capacity is must more than 0");
            }
            keyNodeMap = new HashMap<K,Node<K,V>>();
            nodeList = new NodeDoubleLinkList<K,V>();
            this.capacity = capacity;
        }
        public V get(K key){
            if(keyNodeMap.containsKey(key)){
                Node<K, V> kvNode = keyNodeMap.get(key);
                nodeList.moveToTail(kvNode);
                return kvNode.value;
            }
            return null;
        }

        public void set(K key,V value){
            if(keyNodeMap.containsKey(key)){
                Node<K, V> kvNode = keyNodeMap.get(key);
                kvNode.value = value;
                nodeList.moveToTail(kvNode);
            }else {
                if(keyNodeMap.size() == capacity){
                    removeMostUnusedCache();
                }
                Node<K,V> newNode = new Node<>(key, value);
                keyNodeMap.put(key,newNode);
                nodeList.addTail(newNode);
            }
        }
        /**
         * 删除不常用的数据
         */
        private void removeMostUnusedCache() {
            Node<K, V> kvNode = nodeList.removeHead();
            keyNodeMap.remove(kvNode.key);
        }
        //-----------------------------------------------
    }





}

